'''
难度 中等
题目链接 https://leetcode.cn/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/description/
'''

from typing import List

class Solution:
    def __init__(self) -> None:
        # 标记节点是否被遍历
        self.mark = []
        # 记录所有点之间的联通关系图
        self.graph = []
        # 节点个数
        self.n = 0
    
    def slove(self) -> int:
        res = 0
        for i in range(self.n):
            if self.mark[i]:
                continue
            '''
            这个回路与其他的点都不互通，结果的和就要加上：
            C(m, 1) * C(n - m, 1) // 2
            '''
            count = self.dfs(i)
            # print(i, count)
            res += count * (self.n - count)
        
        return res // 2
    
    # 深度优先递归
    def dfs(self, x: int) -> int:
        self.mark[x] = True
        count = 1

        for y in self.graph[x]:
            # 如果被重复标记
            if not self.mark[y]:
                # print(count)
                count += self.dfs(y)
        
        return count



    # 深度优先解法
    def countPairs(self, n: int, edges: List[List[int]]) -> int:
        # 初始化
        self.mark = [False for _ in range(n)]
        self.graph = [[] for _ in range(n)]
        self.n = n

        for x,y in edges:
            # 相同点联通 放在一起
            self.graph[x].append(y)
            self.graph[y].append(x)
            # print(self.graph)

        return self.slove()

if __name__ == '__main__':
    s = Solution()
    参数 = [
        [3, [[0,1],[0,2],[1,2]]],
        [7, [[0,2],[0,5],[2,4],[1,6],[5,4]]],
    ]
    预期 = [
        0,
        14,
    ]
    for k,v in enumerate(参数):
        r = s.countPairs(v[0], v[1])
        if r != 预期[k]:
            print("第{}个case不通过 期望={} 结果={}\n".format(
                k+1,
                预期[k],
                r
            ))